﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TSP
{
    /// <summary>
/// Struktura danych dla problemu Union-Find
/// </summary>
/// <remarks>
/// W C# to oczywiście klasa, a nie struktura.<br/>
/// To nie jest optymalna wydajnościowo implementacja (ale calkiem dobra !).
/// Implementuje kompresję ścieżek, nie implementuje łączenia wegług rang.<br/>
/// Implementacja ta jest za to zdecydowanie najprostsza (żadna z metod nie ma więcej niż 2 linie kodu! 
/// - nie licząc nagłówka i nawiasów {}).<br/>
/// Wymaga aby badane elementy były identyfikowane za pomocą liczb całkowitych 0,1,...,n-1 (dla problemu rozmiaru n).
/// </remarks>
public class UnionFind
    {
    private int[] gr;

    /// <summary>
    /// Inicjuje dane
    /// </summary>
    /// <param name="n">Rozmiar problemu</param>
    public UnionFind(int n)
        {
        gr = new int[n];
        for ( int i=0 ; i<n ; ++i ) gr[i]=i;
        }

    /// <summary>
    /// Łączy dwa zbiory
    /// </summary>
    /// <param name="n1">Element pierwszego zbioru</param>
    /// <param name="n2">Element drugiego zbioru</param>
    /// <remarks>
    /// Działa prawidłowo również gdy oba argumenty pochodzą z tego samego zbioru.
    /// </remarks>
    public void Union(int n1, int n2)
        {
        gr[Find(n2)]=Find(n1);
        }

    /// <summary>
    /// Znajduje reprezentanta zbioru
    /// </summary>
    /// <param name="n">Dowolny element</param>
    /// <returns>Reprezentant danego elementu</returns>
    /// <remarks>
    /// Wykonuje kompresję ścieżki.
    /// </remarks>
    public int Find(int n)
        {
        if ( gr[gr[n]]!=gr[n] ) gr[n]=Find(gr[n]);
        return gr[n];
        }

    }  //  class UnionFind

}
}
